import com.kiwi.nixu.common.LNode;
import com.sun.xml.internal.ws.handler.HandlerException;

/**
 * 单链表相交指的是两个链表存在完全重合的部分
 */
public class L如何判断两个无环单链表是否交叉 {


    /**
     * 方法三：
     * 尾结点法主要思路：
     * 如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形（如上图所示）。
     * 所以，判断两个链表的最后一个结点是不是相同即可。
     * 即先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，
     * 这时记下两个链表的长度n1、n2，再遍历一次，长链表结点先出发前进|n1-n2|步，之后两个链表同时前进，
     * 每次一步，相遇的第一点即为两个链表相交的第一个点。实现代码如下
     */

    public static LNode isIntersect(LNode head1, LNode head2) {
        if (head1 == null || head1.next == null || head2 == null || head2.next == null || head1 == head2) {
            return null;
        }
        LNode temp1 = head1.next;
        LNode temp2 = head2.next;
        int n1 = 0, n2 = 0;
        //遍历head1，找到尾结点，同时记录head1的长度
        while (temp1.next != null) {
            temp1 = temp1.next;
            ++n1;
        }
        //遍历head1，找到尾结点，同时记录head1的长度
        while (temp2.next != null) {
            temp2 = temp2.next;
            ++n2;
        }

        //head1与head2有相同的尾结点
        if (temp1 == temp2) {
            //长链表先走|n1-n2|步
            if (n1 > n2) {
                while (n1 - n2 > 0) {
                    head1 = head1.next;
                    --n1;
                }
            }

            if (n2 > n1) {
                while (n2 - n1 > 0) {
                    head2 = head2.next;
                    --n2;
                }
            }
            while (head1 != head2) {
                head1 = head1.next;
                head2 = head2.next;
            }
            return head1;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        int i = 1;
        LNode head1 = new LNode();
        head1.next = null;
        LNode head2 = new LNode();
        head2.next = null;
        LNode tmp = null;
        LNode cur = head1;
        LNode p = null;
        for (; i < 8; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
            if (i == 5) {
                p = tmp;
            }
        }
        cur = head2;
        for (i = 1; i < 5; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        //使他们相较于节点5
        cur.next = p;
        LNode interNode = isIntersect(head1, head2);
        if (interNode == null) {
            System.out.println("这两个链表不想交:");
        } else {
            System.out.println("这两个链表相交点为：" + interNode.data);
        }
    }


}
